1. Field of the Invention
This invention relates to electronically determining an orientation for each of a number of objects, more particularly for solving systems of discrete rotation and reflection constraints in determining the orientations of the objects.
2. Related Art
Many applications, such as the physical design of electronic integrated circuits, involve choosing an orientation for each of a number of objects in two dimensions. The orientation of an object can be described by a finite series of clockwise rotations and/or reflections about the X axis or Y axis.
For clarity of exposition, focus on the rectilinear model, in which only horizontal and vertical lines are allowed, since most integrated circuits are fabricated under this model. In the rectilinear model, there are eight (8) possible orientations of an object, as shown in FIG. 1. It is often desirable to place constraints on the orientation of an object, or on the relative orientation of sets of two or more objects. In particular, the following types of constraints are defined:
A single object has a fixed orientation set to one of the eight orientations. PA1 Every object in a set of two or more must have the same orientation. PA1 A pair of objects must have a mirrored orientation about the X axis or the Y axis. PA1 Every object in a set of two or more must have either same or mirrored orientation, and if mirrored, must be mirrored about either the X axis or the Y axis.
A problem which must be solved is as follows: given a set of objects and a set of constraints on these objects, where each constraint is one of the four described above, choose an orientation for each object such that all the constraints are satisfied. A solution to this problem can be easily generalized to other types of orientation constraints and other sets of possible orientations.
For some sets of constraints, it may not be possible to satisfy all the constraints. An overconstraint is a set of constraints that cannot all be satisfied simultaneously. For example, one simple overconstraint would be if there were both a same orientation and a mirrored orientation constraint on the same pair of objects A and B. Clearly B cannot have both the same orientation as A and a mirrored orientation from A. Thus, this pair of constraints forms an overconstraint.
Overconstraints are handled by choosing one of the constraints involved and relaxing it--i.e., turning it off. The exact selection of which constraint in an overconstraint to relax should be made by a procedure separate from the algorithm, in some application-specific way; i.e., the user may have a predetermined preference as to how the choice is made about which constraint to relax.
A known algorithm (the "iterative algorithm") currently employed to solve this problem begins by setting the orientations of objects on which there are fixed orientation constraints. It then iteratively sets the orientations of objects that share constraints with objects whose orientations have already been set. More precisely, and referring to FIGS. 2A and 2B, after starting at step 26, begin by setting each object's orientation to undefined (step 28). Now set the -orientations of the objects on which there are fixed orientation constraints (step 30). Then, repeat the following: find a constraint (step 32) that contains some objects whose orientations have already been set and set the orientations of the other objects in the constraint appropriately (step 42). For same or mirrored orientation constraints (step 34), arbitrarily choose the same orientation (step 38) if either is acceptable (step 36), otherwise choose the only acceptable orientation (step 40).
Check (step 44) whether the orientations are consistent with the desired orientations. If all vertices have been assigned an orientation (step 48), end the process (step 50). When an iteration passes in which no orientations are updated, then find (step 52) a new object with an undefined orientation, set it to a default orientation, and return to step 32. If it is necessary to set the orientation of an object to a different orientation than one to which it is already set (step 44), then this is an overconstraint, and the current constraint is relaxed (step 46). The process returns to step 32.
Unfortunately, there are situations where the arbitrary way that same or mirrored orientation constraints are enforced can lead to the algorithm finding no solution even though one exists. For example, consider four objects A, B, C, and D. Objects A and D have a fixed orientation set to that shown as (a) in FIG. 1. Objects A and B have a same or mirrored orientation constraint about the Y axis, as do objects C and D. Objects B and C have a mirrored orientation constraint about the Y axis. The iterative algorithm first sets the orientations of A and D to (a). But then, regardless of whether it chooses to enforce the same or mirrored orientation constraints as same or mirrored, it will set the orientations of B and C to be the same, and the mirrored orientation constraint between them will not be satisfied.
The iterative algorithm has a time complexity O((n+m).sup.2). where n is the number of objects and m is the number of constraints.